package developer.笔试题.替换通配符;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhangyongkang
 * @time 2025/7/19 14:49
 * @description 替换字符串中的通配符？
 * <p>
 * 给定字符串（合法字符只包括0，1，？）替换字符串中的通配符？为0或 者1，生成所有可能的字符串。
 * <p>
 * Input str = “1??0?101”
 */
public class Change {


    public static void main(String[] args) {
        Solution solution = new Solution();
        List<String> generate = solution.generate("1??0?101");
        generate.forEach(System.out::println);
    }

    static class Solution {
        public List<String> generate(String str) {
            ArrayList<String> result = new ArrayList<>();
            StringBuilder stringBuilder = new StringBuilder(str);
            dfs(stringBuilder, 0, result);
            System.out.println(stringBuilder.toString());
            return result;
        }


        private void dfs(StringBuilder current, int idx, List<String> result) {
            int length = current.length();
            if (idx == length) {
                result.add(current.toString());
                return;
            }
            char c = current.charAt(idx);
            if (c == '?') {//设置好后再递归
                current.setCharAt(idx, '0');
                dfs(current, idx + 1, result);
                current.setCharAt(idx, '1');
                dfs(current, idx + 1, result);
                current.setCharAt(idx, '?');
            } else {
                //直接递归
                dfs(current, idx + 1, result);
            }
        }
    }

}
